/**
 * Created with IntelliJ IDEA.
 * Description:数组中的逆数对
 * User: wangxin
 * Date: 2024-11-02
 * Time: 21:20
 */
public class test1 {
    //方法一：时间复杂度：N^2
    public int InversePairs (int[] nums) {
        // write code here
        int n = nums.length;
        long s = 0;
        for(int i =1; i < n ;i++){
            for(int j =0;j < i;j++){
                if(nums[j] > nums[i]){
                    s++;
                }
            }
        }
        s = s % 1000000007;
        return (int)s;
    }
    //方法二：时间复杂度：nlogn
    public int mod = 1000000007;
    public int mergeSort(int left,int right,int[] data,int[] temp){
        if(left >= right){
            return 0;
        }
        int mid = (left + right) / 2;
        int res = mergeSort(left,mid,data,temp) + mergeSort(mid +1,right,data,temp);
        res = res % mod;
        int i = left; int j = mid + 1;
        for(int k = left; k <= right;k++){
            temp[k] = data[k];
        }
        for(int k = left; k <= right;k++){
            if(i == mid + 1){
                data[k] = temp[j++];
            }else if(j == right + 1 || temp[i] <= temp[j]){
                data[k] = temp[i++];
            }else{
                data[k] = temp[j++];
                res = res + mid - i + 1;
            }
        }
        return res % mod;
    }
    public int InversePairs2 (int[] nums) {
        // write code here
        int n = nums.length ;
        int[] res = new int[n];
        return mergeSort(0,n- 1,nums,res);

    }
}
